package hdoj;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AwayFromHDU1429 {

	private static final char OBSTACLE = '*';
	private static final char START = '@';
	private static final char EXIT = '^';
	
	public static final int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
	private static final int MAX = 20; 
	
	private int minMinute = Integer.MAX_VALUE;
	
	private int rows, columns; 
	private char[][] maze = new char[MAX][MAX];
	
	private int[][] steps = new int[MAX][MAX];
	private int[][] keys = new int[MAX][MAX];
	private boolean[][][] visited = new boolean[21][21][1030];
	
	
	//魔王每隔多少时间来视察一次
	private int t;
	
	public static void main(String[] args) {
		AwayFromHDU1429 object = new AwayFromHDU1429();
		object.getRes();
	}
	
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			rows = scanner.nextInt();
			columns = scanner.nextInt();
			t = scanner.nextInt();
			int startX = 0, startY = 0;
			minMinute = Integer.MAX_VALUE;
			for (int i = 0; i < rows; i++) {
				String string = scanner.next();
				int index = string.indexOf(START);
				if(startX == 0 && index != -1){
					startX = i;
					startY = index;
				}
				maze[i] = string.toCharArray();
				Arrays.fill(steps[i], Integer.MAX_VALUE);
				Arrays.fill(keys[i], 0);
			}
			//
			steps[startX][startY] = 0;
//			dfs(startX, startY);
			bfs(startX, startY);
			if(minMinute == Integer.MAX_VALUE || minMinute >= t){
				System.out.println(-1);
			}else{
				System.out.println(minMinute);
			}
		}
		scanner.close();
	}
	
	//dfs真的不适合用来解迷宫的问题吗，每次写df都感觉不正确
	public void dfs(int x, int y){
		// System.out.println(" x: " + x + " y : " + y + " minute: " + steps[x][y] + " key: " + keys[x][y]);
		if(maze[x][y] == EXIT && steps[x][y] < t){
			minMinute = Math.min(steps[x][y], minMinute);
			return;
		}
		
		for(int i = 0; i < dir.length; i++){
			int curX = x + dir[i][0];
			int curY = y + dir[i][1];
			if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || maze[curX][curY] == OBSTACLE){
				continue;
			}
			
			//怎样判断不重复进入某一个点呢
			//我的想法是判断keys是否要多于或者step是否小于
//			6 6 20
//			@.*...
//			....*.
//			..**..
//			.....a
//			**....
//			^A....
			//看题解，原来是判断有相同钥匙的时候是否走过
//			if(getOneCount(keys[curX][curY]) >= getOneCount(keys[x][y]) && steps[curX][curY] <= 
//					steps[x][y] + 1){
//				continue;
//			}
			//钥匙是上一步的钥匙
			keys[curX][curY] = keys[x][y];
			//当遇到钥匙时
			if(maze[curX][curY] >= 'a' && maze[curX][curY] <= 'j'){
				//钥匙增加
				keys[curX][curY] |= (1 << maze[curX][curY] - 'a');
				// System.out.println(" cur key： " + keys[curX][curY] + " suo:  " + maze[curX][curY]);
			}
			if(visited[curX][curY][keys[curX][curY]] && steps[curX][curY] <= steps[x][y] + 1){
				continue;
			}
			
			//判断是否是带锁的门
			if(maze[curX][curY] >= 'A' && maze[curX][curY] <= 'J'){
				//当不含该门的钥匙时
				// System.out.println("key： " + keys[curX][curY] + " suo:  " + maze[curX][curY]);
				if( ((1 << maze[curX][curY] - 'A') & keys[curX][curY]) == 0){
					continue;
				}
			}
			steps[curX][curY] = steps[x][y] + 1;
			visited[curX][curY][keys[curX][curY]] = true;
			dfs(curX, curY);
			visited[curX][curY][keys[curX][curY]] = false;
		}
	}
	
	//获取钥匙的个数
	public int getOneCount(int number){
		int res = 0;
		while(number != 0){
			res++;
			number &= (number - 1); 
		}
		return res;
	}
	
	class Node{
		int x, y, key, step;
		Node(){
		}
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	
	// Rutime 764MS
	public void bfs(int x, int y){
		Node node = new Node();
		node.x = x; node.y = y;
		Queue<Node> queue =  new LinkedList<>();
		queue.add(node);
		for (int i = 0; i < visited.length; i++) {
			for (int j = 0; j < visited[0].length; j++) {
				for (int k = 0; k < visited[0][0].length; k++) {
					visited[i][j][k] = false;
				}
			}
		}
		visited[x][y][0] = true;
		while(!queue.isEmpty()){
			node = queue.poll();
			if(maze[node.x][node.y] == EXIT){
				minMinute = node.step;
				return;
			}
			for(int i = 0; i < dir.length; i++){
				int curX = node.x + dir[i][0];
				int curY = node.y + dir[i][1];
				if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || maze[curX][curY] == OBSTACLE){
					continue;
				}
				if(visited[curX][curY][node.key]){
					continue;
				}
//				if(maze[curX][curY] == EXIT){
//					minMinute = node.step + 1;
//					return;
//				}
				Node next = new Node(curX, curY);
				next.key = node.key;
				//next.step = node.step + 1;
				if(maze[curX][curY] >= 'A' && maze[curX][curY] <= 'J') {
                    int c = maze[curX][curY] - 'A';
                    if( (next.key & (1 << c)) != 0) {
                        visited[curX][curY][next.key] = true;
                        next.step = node.step + 1;
                        queue.add(next);
                    }
                }else if(maze[curX][curY] >= 'a' && maze[curX][curY] <= 'j') {
                    int c = maze[curX][curY] - 'a';
                    next.key |= (1 << c);
                    if(!visited[curX][curY][next.key]) {
                    	visited[curX][curY][next.key] = true;
                    	next.step = node.step + 1;
                    	queue.add(next);
                    }
                }else {
                	visited[curX][curY][next.key] = true;
                	next.step = node.step + 1;
                	queue.add(next);
                }
			}
		}
	}
}